package com.chenxys.algorithm.newbie;

import java.util.HashSet;

/**
 * <p>
 *      位图:原理,使用二进制数表示这个数是否存在,如0-63共64个数,可用一个long类型数来进行表示,因为long占用8byte共64bit<br/>
 *      做左移操作时为什么使用1L,不使用1 --> 确保和原数的bit位一致
 * </p>
 *
 * @author Chenxys
 * @version V1.0
 * @Package com.chenxys.algorithm.newbie
 * @date 12/31/23 2:31 PM
 * @Copyright ©
 */
public class BitMap {
    private long[] bits;

    public BitMap(int max) {
        // (max + 64) >> 6 -> (max + 64) / 64 代表需要多少个long才能表示完这些数
        bits = new long[(max + 64) >> 6];
    }

    /**
     * <p>
     *     将一个数,加入到位图中
     * </p>
     * @param num 待加入位图的数
     */
    public void add (int num) {
        // num >> 6 定位num在数组中的位置,并将相应bit位置1[那个整数]
        // (num % 63) == (num & 63) --> 计算左移位数
        // 然后将1L左移到相应位置再与原整数相或,则将相应位置为1
        bits[num >> 6] |= (1L << (num & 63));
    }

    /**
     * <p>
     *     将一个数从位图中删除
     * </p>
     * @param num 待删除数
     */
    public void delete(int num) {
        // num >> 6 --> 找到待删除存在那个数里
        // ~(1L << (num & 63)) --> 将1移动到代表这个数的位置,再取反
        // 再与原数相&,因为原数这个位置为1,和0相与则将此位置为0[代表删除]
        bits[num >> 6] &= ~(1L << (num & 63));
    }

    /**
     * <p>
     *     判断一个数是否存在
     * </p>
     * @param num 待判断数
     * @return 是否存在
     */
    public boolean contains(int num) {
        // 1L << (num & 63) 新数,在0～63上的表示方法
        // 找个这个数,再和新数相与,如果结果为1,则存在,为0则不存在
        return (bits[num >> 6] & (1L << (num & 63))) != 0;
    }

    public static void main(String[] args) {
        System.out.println("Test Begin！");
        int max = 10000;
        BitMap bitMap = new BitMap(max);
        HashSet<Integer> set = new HashSet<>();
        int testTime = 10000000;
        for (int i = 0; i < testTime; i++) {
            int num = (int) (Math.random() * (max + 1));
            double decide = Math.random();
            if (decide < 0.333) {
                bitMap.add(num);
                set.add(num);
            } else if (decide < 0.666) {
                bitMap.delete(num);
                set.remove(num);
            } else {
                if (bitMap.contains(num) != set.contains(num)) {
                    System.out.println("Oops!");
                    break;
                }
            }
        }
        for (int num = 0; num <= max; num++) {
            if (bitMap.contains(num) != set.contains(num)) {
                System.out.println("Oops!");
            }
        }
        System.out.println("Test Finish！");
    }
}
